#ifndef __IM_ARRAY_H__
#define __IM_ARRAY_H__

#include <im_base_types.h>

/**
 * @defgroup IMArray IMArray and IMPtrArray
 * @ingroup PrivateIMBusIME
 * @{
 */

/** @struct IMArray
 *  @brief A simple array to hold arbitrary data.
 *
 *  It's a simple structure instead of an object.
 */

/** @struct IMPtrArray
 *  @brief A simple array to hold one or more pointers.
 *
 *  It's a simple structure instead of an object.
 */

IM_BEGIN_DECLS

typedef struct _IMArray         IMArray;
typedef struct _IMPtrArray      IMPtrArray;

struct _IMArray
{
    IMChar *array;
    IMSize  size;
};

struct _IMPtrArray
{
    IMPointer  *array;
    IMSize      size;
};

/** @brief Adds the value on to the end of the array. The array will grow in size automatically if necessary. */
#define         im_array_append_val(a,v)        im_array_append_vals (a, &(v), 1)
/** @brief Adds the value on to the start of the array. The array will grow in size automatically if necessary. */
#define         im_array_prepend_val(a,v)       im_array_prepend_vals (a, &(v), 1)
/** @brief Inserts an element into an array at the given index. */
#define         im_array_insert_val(a,i,v)      im_array_insert_vals (a, i, &(v), 1)
/** @brief Return the size of an array. */
#define         im_array_size(a)                ((a)->size)
/** @brief Return the element at the given index from an array. */
#define         im_array_index(a,t,i)           (((t*) (a)->array) [(i)])
/** @brief Return the size of a pointer array. */

#define         im_ptr_array_size(a)            ((a)->size)
/** @brief Return the pointer element at the given index from a pointer array. */
#define         im_ptr_array_index(a,index)     (((a)->array)[index])

/** 
 * @brief Create a new IMArray.
 * 
 * @param zero_terminated TRUE if the array should have an extra element at the end which is set to 0.
 * @param clear           TRUE if IMArray elements should be automatically cleared to 0 when they are allocated.
 * @param element_size    the size of each element in bytes.
 * 
 * @return                the new IMArray
 */
IMArray*        im_array_new                        (IMBool              zero_terminated,
                                                     IMBool              clear,
                                                     IMSize              element_size);

/** 
 * @brief Creates a new IMArray with reserved elements preallocated. 
 *
 * This avoids frequent reallocation, if you are going to add many elements to the array. 
 * Note however that the size of the array is still 0.
 * 
 * @param zero_terminated TRUE if the array should have an extra element at the end which is set to 0.
 * @param clear           TRUE if IMArray elements should be automatically cleared to 0 when they are allocated.
 * @param element_size    the size of each element in bytes.
 * @param reserved        number of elements preallocated. 
 * 
 * @return                the new IMArray
 */
IMArray*        im_array_new_reserved               (IMBool              zero_terminated,
                                                     IMBool              clear,
                                                     IMSize              element_size,
                                                     IMSize              reserved);

/** 
 * @brief Destory the IMArray.
 *
 * If array elements contain dynamically-allocated memory, they should be freed first.
 * 
 * @param array       an IMArray 
 * @param free_memory if TRUE the actual element data is freed as well.
 * 
 * @return            the element data if free_memory is FALSE, otherwise NULL
 */
IMChar*         im_array_destroy                    (IMArray            *array,
                                                     IMBool              free_memory);

/** 
 * @brief Clear the IMArray, while the actual element data is not freed.
 *
 * @param array an IMArray
 */
void            im_array_clear                      (IMArray            *array);

/** 
 * @brief Adds len elements onto the end of the array.
 * 
 * @param array an IMArray
 * @param data  a pointer to the elements to append to the end of the array.
 * @param len   the number of elements to append.
 * 
 * @return      the IMArray
 */
IMArray*        im_array_append_vals                (IMArray            *array,
                                                     IMConstPointer      data,
                                                     IMSize              len);

/** 
 * @brief Adds len elements onto the start of the array.
 * 
 * @param array an IMArray
 * @param data  a pointer to the elements to prepend to the start of the array.
 * @param len   the number of elements to prepend.
 * 
 * @return      the IMArray
 */
IMArray*        im_array_prepend_vals               (IMArray            *array,
                                                     IMConstPointer      data,
                                                     IMSize              len);

/** 
 * @brief Inserts len elements into an IMArray at the given index.
 * 
 * @param array an IMArray
 * @param index the index to place the elements at.
 * @param data  a pointer to the elements to insert.
 * @param len   the number of elements to insert.
 * 
 * @return the IMArray
 */
IMArray*        im_array_insert_vals                (IMArray            *array,
                                                     IMSize              index,
                                                     IMConstPointer      data,
                                                     IMSize              len);

/** 
 * @brief Preallocate amount of memory in an IMArray
 * 
 * @param array an IMArray
 * @param size  number of elements preallocated. 
 */
void            im_array_reserve                    (IMArray            *array,
                                                     IMSize              size);

/** 
 * @brief Sets the size of the array, expanding it if necessary. 
 *
 * If the array was created with clear_ set to TRUE, the new elements are set to 0.
 * 
 * @param array an IMArray
 * @param size  the new size of the IMArray
 */
void            im_array_set_size                   (IMArray            *array,
                                                     IMSize              size);

/** 
 * @brief Removes the element at the given index from an IMArray. 
 *
 * The following elements are moved down one place.
 * 
 * @param array an IMArray
 * @param index the index of the element to remove
 * 
 * @return the IMArray
 */
IMArray*        im_array_remove_index               (IMArray            *array,
                                                     IMSize              index);

/** 
 * @brief Removes the element at the given index from an IMArray. 
 *
 * The last element in the array is used to fill in the space, so this function does 
 * not preserve the order of the IMArray. But it's faster than im_array_remove_index().
 * 
 * @param array an IMArray
 * @param index the index of the element to remove
 * 
 * @return the IMArray
 */
IMArray*        im_array_remove_index_fast          (IMArray            *array,
                                                     IMSize              index);

/** 
 * @brief Removes the given number of elements starting at the given index from an IMArray
 * 
 * @param array     an IMArray
 * @param index     the index of the first element to remove
 * @param length    the number of elements to remove
 * 
 * @return          the IMArray
 */
IMArray*        im_array_remove_range               (IMArray            *array,
                                                     IMSize              index,
                                                     IMSize              length);

/** 
 * @brief Sort the IMArray with the given comparison function.
 * 
 * @param array         an IMArray
 * @param compare_func  a qsort(3)-style comparison function
 */
void            im_array_sort                       (const IMArray      *array,
                                                     IMCompareFunc       compare_func);

/** 
 * @brief Just like im_array_sort(), but the comparison function receives an extra 
 *        user data argument.
 * 
 * @param array         an IMArray
 * @param compare_func  a qsort(3)-style comparison function
 * @param user_data     data to pass to compare_func 
 */
void            im_array_sort_with_data             (const IMArray      *array,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);
/**
 * @brief Finds the first position in which a given val could be inserted
 *        without changing the ordering.
 *
 * @param array         an IMArray
 * @param val           the compared value
 * @param compare_func  a qsort(3)-style comparation function
 *
 * @return An index to the first element "not less than" val, or array size
 *         if every element is less than val.
 */
IMSize          im_array_lower_bound                (const IMArray      *array,
                                                     IMPointer           val,
                                                     IMCompareFunc       compare_func);

/**
 * @brief Just like im_array_lower_bound(), but the comparison function receives 
 *        an extra user data argument.
 *        
 *
 * @param array         an IMArray
 * @param val           the compared value
 * @param compare_func  a qsort(3)-style comparation function
 * @param user_data     data to pass to compare_func
 *
 * @return An index to the first element "not less than" val, or array size
 *         if every element is less than val.
 */
IMSize          im_array_lower_bound_with_data      (const IMArray      *array,
                                                     IMPointer           val,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);

/**
 * @brief Finds the last position in which a given val could be inserted
 *        without changing the ordering.
 *
 * @param array         an IMArray
 * @param val           the compared value
 * @param compare_func  a qsort(3)-style comparation function
 *
 * @return An index to the first element greater than val, or array size
 *         if no elements are greater than val.
 */
IMSize          im_array_upper_bound                (const IMArray      *array,
                                                     IMPointer           val,
                                                     IMCompareFunc       compare_func);

/**
 * @brief Just like im_array_upper_bound(), but the comparison function receives 
 *        an extra user data argument.
 *
 * @param array         an IMArray
 * @param val           the compared value
 * @param compare_func  a qsort(3)-style comparation function
 * @param user_data     data to pass to compare_func
 *
 * @return An index to the first element greater than val, or array size
 *         if no elements are greater than val.
 */
IMSize          im_array_upper_bound_with_data      (const IMArray      *array,
                                                     IMPointer           val,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);

/** 
 * @brief Iterate an IMArray with the given function which receives an extra 
 *        user data argument.
 * 
 * @param array      an IMArray
 * @param func       the iterator function
 * @param user_data  data to pass to func
 */
void            im_array_foreach                    (const IMArray      *array,
                                                     IMFunc              func,
                                                     IMPointer           user_data);

/** 
 * @brief Iterate a range of an IMArray with the given function which receives 
 *        an extra user data argument.
 * 
 * @param array      an IMArray
 * @param index      the index of the first element to iterate
 * @param length     the number of elements to iterate
 * @param func       the iterator function
 * @param user_data  data to pass to func
 */
void            im_array_foreach_in_range           (const IMArray      *array,
                                                     IMSize              index,
                                                     IMSize              length,
                                                     IMFunc              func,
                                                     IMPointer           user_data);

/**
 * @brief Create a new IMPtrArray object.
 */
IMPtrArray*     im_ptr_array_new                    ();

/**
 * @brief Create a new IMPtrArray object with specified size.
 */
IMPtrArray*     im_ptr_array_new_reserved           (IMSize              reserved);

/**
 * @brief Destroy an IMPtrArray object.
 *
 * @param free_memory   Whether to free the array memory or not.
 * @return Pointer to the array memory if free_memory is FALSE,
 *         otherwise return 0. The result must be freed by im_free(),
 *         if it's not 0.
 */
IMPointer*      im_ptr_array_destroy                (IMPtrArray         *array,
                                                     IMBool              free_memory);
/**
 * @brief Clear an IMPtrArray.
 */
void            im_ptr_array_clear                  (IMPtrArray         *array);
/**
 * @brief Reserve a specific amount of space,
 *        to prevent reallocation when inserting many
 *        items.
 */
void            im_ptr_array_reserve                (IMPtrArray         *array,
                                                     IMSize              space);
/**
 * @brief Set the size of an IMPtrArray.
 *
 * The memory will not be freed.
 */
void            im_ptr_array_set_size               (IMPtrArray         *array,
                                                     IMSize              size);
/**
 * @brief Free unused memory occupied by an IMPtrArray.
 */
void            im_ptr_array_free_unused_memory     (IMPtrArray         *array);
/**
 * @brief Prepend a pointer into an IMPtrArray.
 */
IMPtrArray*     im_ptr_array_prepend                (IMPtrArray         *array,
                                                     IMPointer           data);
/**
 * @brief Append a pointer into an IMPtrArray.
 */
IMPtrArray*     im_ptr_array_append                 (IMPtrArray         *array,
                                                     IMPointer           data);
/**
 * @brief Insert a pointer into the specific position in an IMPtrArray.
 */
IMPtrArray*     im_ptr_array_insert                 (IMPtrArray         *array,
                                                     IMSize              index,
                                                     IMPointer           data);
/**
 * @brief Remove the pointer at specific position in an IMPtrArray.
 *
 * @return The pointer removed.
 */
IMPointer       im_ptr_array_remove                 (IMPtrArray         *array,
                                                     IMSize              index);
/**
 * @brief Fast remove the pointer at specific position in an IMPtrArray.
 *        Order of elements will not be preserved.
 *
 * @return The pointer removed.
 */
IMPointer       im_ptr_array_remove_fast            (IMPtrArray         *array,
                                                     IMSize              index);
/**
 * @brief Remove a range in an IMPtrArray.
 */
void            im_ptr_array_remove_range           (IMPtrArray         *array,
                                                     IMSize              index,
                                                     IMSize              length);
/**
 * @brief Sort all pointers in an IMPtrArray by using specific
 *        compare function.
 */
void            im_ptr_array_sort                   (IMPtrArray         *array,
                                                     IMCompareFunc       compare_func);
/**
 * @brief Sort all pointers in an IMPtrArray by using specific
 *        compare function and user specific data.
 */
void            im_ptr_array_sort_with_data         (IMPtrArray         *array,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);
/**
 * @brief Finds the first position in which a given val could be inserted
 *        without changing the ordering.
 *
 * @return An index to the first element "not less than" val, or array size
 *         if every element is less than val.
 */
IMSize          im_ptr_array_lower_bound            (const IMPtrArray   *array,
                                                     IMPointer           val,
                                                     IMCompareFunc       compare_func);

/**
 * @brief Just like the im_ptr_array_upper_bound(), but the comparison function 
 *        receives an extra user data argument.
 *
 * @return An index to the first element "not less than" val, or array size
 *         if every element is less than val.
 */
IMSize          im_ptr_array_lower_bound_with_data  (const IMPtrArray   *array,
                                                     IMPointer           data,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);
/**
 * @brief Finds the last position in which a given val could be inserted
 *        without changing the ordering.
 *
 * @return An index to the first element greater than val, or array size
 *         if no elements are greater than val.
 */
IMSize          im_ptr_array_upper_bound            (const IMPtrArray   *array,
                                                     IMPointer           data,
                                                     IMCompareFunc       compare_func);

/**
 * @brief Just like the im_ptr_array_upper_bound(), but the comparison function 
 *        receives an extra user data argument.
 *
 * @return An index to the first element greater than val, or array size
 *         if no elements are greater than val.
 */
IMSize          im_ptr_array_upper_bound_with_data  (const IMPtrArray   *array,
                                                     IMPointer           data,
                                                     IMCompareDataFunc   compare_func,
                                                     IMPointer           user_data);

/**
 * @brief Iterate an IMPtrArray with the given function which receives an extra 
 *        user data argument.
 *
 * @param array      an IMArray
 * @param func       the iterator function
 * @param user_data  data to pass to func
 */
void            im_ptr_array_foreach                (const IMPtrArray   *array,
                                                     IMFunc              func,
                                                     IMPointer           user_data);

/**
 * @brief Iterate a range of an IMPtrArray with the given function which receives 
 *        an extra user data argument.
 *
 * @param array      an IMArray
 * @param index      the index of the first element to iterate
 * @param length     the number of elements to iterate
 * @param func       the iterator function
 * @param user_data  data to pass to func
 */
void            im_ptr_array_foreach_in_range       (const IMPtrArray   *array,
                                                     IMSize              index,
                                                     IMSize              length,
                                                     IMFunc              func,
                                                     IMPointer           user_data);

IM_END_DECLS

#endif
/**  @} */

/*
vi:ts=4:nowrap:ai:expandtab
*/
